/* Copyright 2012 Tobias Marschall
 *
 * This file is part of CLEVER.
 *
 * CLEVER is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * CLEVER is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with CLEVER.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef VARIATIONINDEX_H_
#define VARIATIONINDEX_H_

#include <vector>
#include <boost/unordered_map.hpp>

#include "Variation.h"

/** Index structure over a set of variations able to quickly answer
 *  "contained-in queries". That is, given an interval, it can (quickly)
 *  return all variations contained in that interval. */
class VariationIndex {
private:
	typedef enum { INSERTION, DELETION_START, DELETION_END } event_type_t;
	typedef struct event_t {
		size_t position;
		size_t variation_index;
		event_type_t type;
		event_t(size_t position, size_t variation_index, event_type_t type) : position(position), variation_index(variation_index), type(type) {}
	} event_t;
	typedef struct {
		bool operator() (const event_t& e1, const event_t& e2) { return (e1.position<e2.position);}
	} event_compare_t;
	// a record of this type is kept for each chromosome
	typedef struct {
		std::vector<event_t> events;
		// in distances of step_size, this vector stores the index of the
		// next event in the event list after the given position;
		// e.g. active_events[n] gives the index of the first event
		// after position n*step_size
		std::vector<size_t> event_list_indices;
	} chromosome_record_t;
	// Mapping chromosome names to sorted lists of events
	boost::unordered_map<std::string, chromosome_record_t> chromosomes;
	size_t step_size;
public:
	/** Indexes the given variations and keeps a reference to them. That is, the given
	 *  reference must be valid throughout the lifetime of this object. */
	VariationIndex(const std::vector<Variation>& variations);
	virtual ~VariationIndex();

	/** Returns the set of indices (w.r.t. to the vector given at construction time) of
	 *  variations completely contained in the interval from start to end.
	 *  start/end are interpreted as positions between two characters, that is, a value n
	 *  refers to the position between character n and n-1. Returns a null pointer when there
	 *  are no variations in that region. */
	std::auto_ptr<std::vector<size_t> > containedIn(const std::string& chromosome, size_t start, size_t end);
};

#endif /* VARIATIONINDEX_H_ */
